package com.ocean.stack;

import java.util.*;

/**
 * https://leetcode.cn/problems/valid-parentheses/
 * 有效的括号
 */
public class ValidParentheses2 {
    public static void main(String[] args) {
        ValidParentheses2 validParentheses = new ValidParentheses2();
        String str = "([{}])";
        System.out.println(validParentheses.isValid(str));
    }

    public boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {
            {
                put(']', '[');
                put('}', '{');
                put(')', '(');
            }
        };
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (map.containsKey(cur)) {
                if (deque.isEmpty() || !deque.peek().equals(map.get(cur))) {
                    return false;
                }
            } else {
                deque.push(cur);
            }
        }
        return true;
    }
}
